from typing import List

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        n = len(nums)
        if target in nums:
            return nums.index(target)
        elif target < nums[0]:
            return 0
        elif target > nums[n-1]:
            return n 
        else:
            left = 0
            right = n-1
            while left <= right:
                mid = (left+right)//2
                if nums[mid] < target:
                    left = mid+1
                elif nums[mid] > target:
                    right = mid-1
                elif left == right+1:
                    return left
                elif right == left+1:
                    return right
                elif left == right:
                    return left+1
            return left

    def searchInsert2(self, nums: List[int], target: int) -> int:
        n = len(nums)
        left = 0
        right = n - 1
        ans = n
        while left <= right:
            mid = ((right - left) >> 1) + left
            if target <= nums[mid]:
                ans = mid
                right = mid - 1
            else:
                left = mid + 1
        return ans


print(Solution().searchInsert2([1,4,7,8,9,11,13], 5))

'''
复杂度分析

时间复杂度：O(logn)，其中 n 为数组的长度。二分查找所需的时间复杂度为 O(logn)。

空间复杂度：O(1)。我们只需要常数空间存放若干变量。
'''